package com.arron.algorithm.leetcodetop100.技巧;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class 丑数II {


    public int nthUglyNumber(int n) {

        int[] factors = {2,3,5};
        //用于去除重复元素
        Set<Long> set = new HashSet<>();

        // 使用最小堆来实现自动排序 ，每次取出堆顶元素
        PriorityQueue<Long> queue = new PriorityQueue<>();

        //初始化
        set.add(1L);
        queue.offer(1L);

        Long res = 0L;

        for (int i = 0; i < n; i++) {

            Long cur = queue.poll();
            res = cur;
            for (int factor : factors) {

                Long next = cur * factor;
                if (set.add(next)){
                    queue.offer(next);
                }
            }

        }
        return res.intValue();
    }


    /**
     *  动态规划
     * @param n
     * @return
     */
    public int nthUglyNumber_plus(int n) {


        int[] dp = new int[n];

        //base case
        dp[0] = 1;

        //状态转移方程

        int a =0,b=0,c=0;
        for (int i = 1; i < n;i++) {

            a= dp[a] *2;
            b = dp[b] *3;
             c = dp[c] *5;

            dp[i] = Math.min(a,Math.min(b,c));


            if (dp[i]  == a) a++;
            if (dp[i]  == b) b++;
            if (dp[i]  == c) c++;
        }
        return dp[n-1];
    }



    public static void main(String[] args) {
        丑数II ii = new 丑数II();


        int i = 8;

        System.out.println((i-1)>>>1);


        System.out.println(ii.nthUglyNumber(1500));

    }
}
